package demo1;

import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {


    //最大数
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = ""+nums[i];
        }
        Arrays.sort(strs,(a,b)->
        {
            return (b+a).compareTo(a+b);
        });
        StringBuilder ret = new StringBuilder();
        for(String each : strs) ret.append(each);
        if(ret.charAt(0)=='0') return "0";
        return ret.toString();
    }

    //将数组和减半的最小次数
    public int halveArray(int[] nums) {
        PriorityQueue<Double> queue = new PriorityQueue<>((a,b)-> b.compareTo(a));
        double sum = 0.0;
        for(int each : nums){
            sum += each;
            queue.offer((double)each);
        }
        sum = sum/2.0;
        int count = 0;
        while (sum > 0) {
            double val = queue.poll()/2.0;
            sum -= val;
            count++;
            queue.offer(val);
        }
        return count;
    }

    //柠檬水找零
    public boolean lemonadeChange(int[] bills) {
        int five = 0;int ten = 0;
        for(int each : bills){
            if(each==5) five++;
            else if(each==10){
                if(five!=0) five--;
                else return false;
            }else {
                if(five!=0 && ten != 0) {
                    ten--;
                    five--;
                }else if(five>=3)
                    five-=3;
                else return false;
            }
        }
        return true;
    }

    public boolean lemonadeChange1(int[] bills) {
        if(bills[0]!=5) return false;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(5,1);
        map.put(10,0);
        for (int i = 1; i < bills.length; i++) {
            if(bills[i]==5)
                map.put(5,map.getOrDefault(5,0)+1);
            else if(bills[i]==10){
                if(map.get(5)==0) return false;
                else map.put(5,map.get(5)-1);
                map.put(10,map.get(10)+1);
            }else {
                if(map.get(10)!=0){
                    if(map.get(5)==0) return false;
                    else {
                        map.put(10,map.get(10)-1);
                        map.put(5,map.get(5)-1);
                    }
                }else {
                    map.put(5,map.get(5)-3);
                    if(map.get(5)<0) return false;
                }
            }
        }
        return true;
    }
}




















